# Einfügesortieralgorithmus
Übersicht
Einfügesortierung ist ein einfacher Sortieralgorithmus, bei dem jedes Element eines Arrays an der richtigen Position im Array eingefügt wird. Es beginnt mit einem leeren sortierten Array und durchläuft dann das Eingabearray, wobei jedes Element an der richtigen Position im sortierten Array eingefügt wird. Dieser Vorgang wird wiederholt, bis das gesamte Eingabearray sortiert ist.
Algorithmusschritte
Hier ist der Schritt-für-Schritt-Algorithmus für die Einfügungssortierung:
1. Beginnen Sie mit einem leeren sortierten Array.
2. Durchlaufen Sie das Eingabearray.
3. Fügen Sie jedes Element im Eingabearray an der richtigen Position im sortierten Array ein.
4. Um ein Element einzufügen, vergleichen Sie es mit jedem Element im sortierten Array, beginnend mit dem ersten Element.
5. Wenn das Element kleiner als das aktuelle Element im sortierten Array ist, fügen Sie es vor dem aktuellen Element ein.
6. Wenn das Element größer als das aktuelle Element im sortierten Array ist, fahren Sie mit dem Vergleich mit dem nächsten Element im sortierten Array fort.
7. Wiederholen Sie die Schritte 4 bis 6, bis das Element an der richtigen Position im sortierten Array eingefügt wurde.
8. Wiederholen Sie die Schritte 2–7 für jedes Element im Eingabearray.
Beispiel
Betrachten wir das folgende Eingabearray:
„
[5, 2, 8, 3, 1]
„
Die folgenden Schritte zeigen, wie der Einfügungssortierungsalgorithmus dieses Array sortieren würde:
1. Beginnen Sie mit einem leeren sortierten Array.
„
[]
„
2. Durchlaufen Sie das Eingabearray.
„
[5]
„
3. Fügen Sie jedes Element im Eingabearray an der richtigen Position im sortierten Array ein.
„
[5]
„
4. Um das Element 2 einzufügen, vergleichen Sie es mit jedem Element im sortierten Array, beginnend mit dem ersten Element.
„
[5, 2]
„
5. Da 2 kleiner als 5 ist, fügen Sie es vor dem aktuellen Element ein.
„
[2, 5]
„
6. Durchlaufen Sie das Eingabearray.
„
[2, 5, 8]
„
7. Fügen Sie jedes Element im Eingabearray an der richtigen Position im sortierten Array ein.
„
[2, 5, 8]
„
8. Um das Element 3 einzufügen, vergleichen Sie es mit jedem Element im sortierten Array, beginnend mit dem ersten Element.
„
[2, 3, 5, 8]
„
9. Da 3 kleiner als 5 ist, fügen Sie es vor dem aktuellen Element ein.
„
[2, 3, 5, 8]
„
10. Durchlaufen Sie das Eingabearray.
„
[2, 3, 5, 8, 1]
„
11. Fügen Sie jedes Element im Eingabearray an der richtigen Position im sortierten Array ein.
„
[1, 2, 3, 5, 8]
„
12. Um das Element 1 einzufügen, vergleichen Sie es mit jedem Element im sortierten Array, beginnend mit dem ersten Element.
„
[1, 2, 3, 5, 8]
„
13. Da 1 kleiner als 2 ist, fügen Sie es vor dem aktuellen Element ein.
„
[1, 2, 3, 5, 8]
„
14. Das sortierte Array ist nun vollständig.
„
[1, 2, 3, 5, 8]
„
Zeitkomplexität
Die zeitliche Komplexität der Einfügungssortierung beträgt O(n^2), wobei n die Länge des Eingabearrays ist. Dies bedeutet, dass die Laufzeit der Einfügungssortierung quadratisch zunimmt, wenn die Größe des Eingabearrays zunimmt. Die Einfügungssortierung erzielt die beste Leistung, wenn das Eingabearray bereits nahezu sortiert ist. In diesem Fall beträgt die zeitliche Komplexität O(n).
Weltraumkomplexität
Die Einfügungssortierung erfordert O(1) Hilfsraum, da zusätzlich zum Eingabearray nur eine einzige Variable (das aktuell eingefügte Element) gespeichert werden muss.
Vor- und Nachteile
Einfügungssortierung hat einige Vor- und Nachteile:
Vorteile:
* Einfach zu implementieren
* Effizient für kleine Arrays oder nahezu sortierte Arrays
* Stabiler Sortieralgorithmus (behält die relative Reihenfolge gleicher Elemente bei)
Nachteile:
* Nicht effizient für große Arrays
* Quadratische Zeitkomplexität (O(n^2))
* Kein In-Place-Sortieralgorithmus (erfordert zusätzlichen Platz)
Schlussfolgerung
Einfügungssortierung ist ein einfacher und effizienter Sortieralgorithmus, der sich gut für kleine Arrays oder nahezu sortierte Arrays eignet. Seine Einfachheit und Stabilität machen ihn zu einem nützlichen Algorithmus für Bildungszwecke und für spezielle Anwendungen. Allerdings ist es nicht der effizienteste Sortieralgorithmus für große Arrays, wo effizientere Algorithmen wie Quicksort oder Mergesort verwendet werden sollten.
